§ 1.1 Field of the Invention
The present invention concerns routing protocols. In particular, the present invention concerns routing protocols for use in networks employing at least some nodes having redundant routing facilities.
§ 1.2 Description of Related Art
The description of art in this section is not, and should not be interpreted to be, an admission that such art is prior art to the present invention.
Many large networks are made up of interconnected nodes (referred to as “routers” below without loss of generality). The routers may be geographically distributed throughout a region and connected by links (e.g., optical fiber, copper cable, wireless transmission channels, etc.). In such a network, each router typically interfaces with (e.g., terminates) multiple input links and multiple output links. Addressed data (referred to as “packets” below without loss of generality) traverse the network by being forwarded from router to router until they reach their destinations (as typically specified in by so-called layer-3 addresses in the packet headers). Unlike nodes in a “circuit-switched” network, which establish a connection for the duration of a “call” or “session” to send data received on a given input port out on a given output port, routers determine the destination addresses of received packets and, based on these destination addresses, determine, in each case, the appropriate output link on which to send them. Since, unlike nodes in a “circuit-switched” network, routers are not connection-based, packets having the same destination address may actually traverse different paths through the network.
Basically, known routing protocols function to (i) accept network state information, (ii) update resident network topology information based on such accepted information, (iii) disseminate network state information, (iv) generate paths (e.g., routes) based on the resident network topology information, and (v) generate forwarding information based on the paths. Changes to the network are propagated throughout the network, and nodes of the network will update their resident network topology information accordingly. Such a change to the network may occur when a node fails. Many of such failures are attributable to software failures. As nodes fail and subsequently recover, such changes will be propagated through the network. Depending upon the size of the network, the topology of the network, and signaling used within the network, it may take some time following a change before the network or a node thereof reaches a stable state.